Digital halftoning, sometimes referred to as "spatial dithering", is the process of creating a binary approximation to a sampled gray scale image. Sampled gray scale values are typically quantized to have one of a discrete number of values, e.g., 256 or 1024 values. The basic idea in digital halftoning is to replace these quantized picture elements (pixels) from a region of the gray scale image having an average value of x (where 0=white and 1=black) with a binary pattern of 1s and 0s. Halftoning works because the eye perceives a set of closely spaced black and white spots as a shade of gray. Alternately, it may be said that the eye acts as if it contains a spatial low pass filter.
In accordance with one halftoning technique, the fraction of resulting 1s is approximately x. The binary pattern is then conveniently used with a display device such as a CRT display or a printer to produce the values for the pixels in the gray scale halftone image. If the 1s and 0s are supplied to a printer where the 1s are printed as black spots and spaces are sufficiently close together, the eye averages the black spots and white spaces to perceive, approximately, gray level x. In so perceiving the image, the eye exhibits a low-pass filtering characteristic. The number of gray scale samples (pixels) is advantageously equal to the number of bits in the binary pattern.
Recent years have witnessed increasing demand for digital storage and transmission of gray scale images. In part, this is due to the increasing use of laser printers having a resolution of, e.g., 600 spots (dots) per inch, to produce halftone approximations to gray scale images such as photographs, art work, design renderings, magazine layouts, etc. The conventional approach to achieving high quality halftone images is to use a high resolution printer. However, the printer resolution required for transparent halftoning with prior art techniques is of the order of 1400 dots/inch. Such printers are often slow and expensive.
Many prior art halftoning techniques assume that the black area of a printed binary pattern is proportional to the fraction of 1s in the pattern. This means that the area occupied by each black dot is roughly the same as the area occupied by each white dot. Thus, the "ideal" shape for the black spots produced by a printer (in response to 1s) would be T.times.T squares, where T is the spacing between the centers of possible printer spots. However, most practical printers produce approximately circular spots. It is clear, therefore, that the radius of the dots must be at least T/.sqroot.2 so that an all-1s binary pattern is capable of blackening a page entirely. This has the unfortunate consequence of making black spots cover portions of adjacent spaces, causing the perceived gray level to be darker than the fraction of 1s. Moreover, most printers produce black spots that are larger than the minimal size (this is sometimes called "ink spreading"), which further distorts the perceived gray level. The most commonly used digital halftoning techniques (for printing) protect against such ink spreading by clustering black spots so the percentage effect on perceived gray level is reduced. Unfortunately, such clustering constrains the spatial resolution (sharpness of edges) of the perceived images and increases the low-frequency artifacts. There is a tradeoff between the number of perceived gray levels and the visibility of low-frequency artifacts.
Block replacement is one commonly used halftoning technique used to improve perceived and gray scale images. Using this technique, the image is subdivided into blocks (e.g. 6.times.6 pixels) and each block is "replaced" by one of a predetermined set of binary patterns (having the same dimensions as the image blocks). Binary patterns corresponding to the entire image are then supplied to a printer or other display device. Typically, the binary patterns in the set have differing numbers of 1s, and the pattern whose fraction of 1s best matches the gray level of the image block is selected. This block replacement technique is also referred to as pulse-surface-area modulations.
In another halftoning technique known as screening, the gray scale array is compared, pixel by pixel, to an array of thresholds. A black dot is placed wherever the image gray level is greater than the corresponding threshold. In the so-called random dither variation of this technique, the thresholds are randomly generated. In another variation, ordered dither, the thresholds are periodic. More specifically, the threshold array is generated by periodically replicating a matrix (e.g. 6.times.6) of threshold values.
A technique known as error diffusion is used in non-printer halftone display contexts to provide halftoning when ink spreading and other distortions common to printers are not present. Like most of the known halftoning schemes, error diffusion makes implicit use of the eye model. It shapes the noise, i.e., the difference between the gray scale image and the halftone image, so that it is not visible by the eye. The error diffusion technique produces noise with most of the noise energy concentrated in the high frequencies, i.e., so-called blue noise. Thus, it minimizes the low-frequency artifacts. However, since error diffusion does not make explicit use of the eye model, it is not easy to adjust when the eye filter changes, for example with printer resolution, or viewer distance. Error diffusion accomplishes good resolution by spreading the dots. It is thus very sensitive to ink spreading, in contrast to the clustered dot schemes like "classical" screening. In the presence of ink spreading, error diffusion often produces very dark images, therefore limiting its application to cases with substantially no ink spreading.
Numerous researchers have estimated the spatial frequency sensitivity of the eye, often called the modulation transfer function (MTF). The eye is most sensitive to frequencies around 8 cycles/degree. Others have variously estimated the peak sensitivity to lie between 3 and 10 cycles/degree. The decrease in sensitivity at higher frequencies is generally ascribed to the optical characteristics of the eye (e.g. pupil size). The sensitivity of the eye drops 3 db from its peak at about 3 and 16 cycles/degree, 20 db at 35 cycles/degree, and about 46 db at 60 cycles/degree. The decrease in sensitivity at low frequencies accounts for the "illusion of simultaneous contrast" (a region with certain gray level appears darker when surrounded by a lighter gray level than when surrounded by a darker) and for the Moch band effect (when two regions with different gray levels meet at an edge, the eye perceives a light band on the light side of the edge and a dark band on the dark side of the edge).
The eye is more sensitive to horizontal or vertical sinusoidal patterns than to diagonal ones. Specifically, it is less sensitive to 45 degree sinusoids, with the difference being about 0.6 db at 10 cycles/degree and about 3 db at 30 cycles/degree. This is not considered to be large, but it is used to good effect in the most commonly used halftoning technique for printers.
Standard error diffusion techniques have several drawbacks. First, errors are propagated which are a significant fraction of a mark. When the diffused error is large, an unpleasing texture results. Second, weighted errors are computed and propagated to adjacent pixels in a slow scan direction. This in turn requires computationally intensive algorithms for clustering and adjusting marks.